package test;

//目标和：https://leetcode.cn/problems/target-sum/

public class FindTargetSumWays {
	
	//DFS,时间复杂度：O(2^n)
	public int sum;
    public int count;
    public void dfs(int[] nums,int target,int pos){
        if(pos==nums.length){
            if(sum==target) 
                count++;
            return ;
        }

        //选+
        sum+=nums[pos];
        dfs(nums,target,pos+1);
        sum-=nums[pos];

        //选-
        sum-=nums[pos];
        dfs(nums,target,pos+1);
        sum+=nums[pos];
    }
    public int findTargetSumWays1(int[] nums, int target) {
        sum=count=0;
        dfs(nums,target,0);
        return count;
    }
	
	//动态规划,时间复杂度：O(n*aim)
	public int findTargetSumWays2(int[] nums, int target) {
		
        int sum=0,n=nums.length;
        for(int x:nums) sum+=x;
        int aim=(sum+target)/2;
        
        if((sum+target)%2!=0||aim<0) return 0;
        
        int[][] dp=new int[n+1][aim+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=aim;j++){   //背包问题j可以从0开始
                dp[i][j]=dp[i-1][j];
                if(j-nums[i-1]>=0)
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][aim];
    }
}
